#ifndef __HASH_TABLE_H__
#define __HASH_TABLE_H__

#include <cstddef>
#include <list>
#include <memory>
#include <utility>
#include <vector>

template <typename Key, typename Value>
class HashTable
{
  public:
    HashTable(const int initialCapcity = 16) : buckets(initialCapcity), count(0)
    {
        // 最小是1
        if (initialCapcity < 1)
        {
            buckets.resize(1);
        }
        for (auto& ele : buckets)
        {
            ele = std::make_shared<List>();
        }
    }

    void insert(const Key& key, const Value& value);

    void remove(const Key& key);

    bool find(const Key& key, Value& value);

    Value& operator[](const Key& key);

    size_t getBucketCount() const { return buckets.size(); }

    size_t size() const { return count; }

  private:
    void resize();

    using List = std::list<std::pair<Key, Value>>;
    using ListPtr = std::shared_ptr<List>;

    std::vector<ListPtr> buckets;
    size_t count;
    const double maxLoadFactor = 0.7;
};

template <typename Key, typename Value>
void HashTable<Key, Value>::insert(const Key& key, const Value& value)
{
    if ((double)count / buckets.size() >= maxLoadFactor)
    {
        resize();
    }

    std::hash<Key> hasher;
    size_t index = hasher(key) % buckets.size();
    auto& listPtr = buckets[index];
    for (auto& it : *listPtr)
    {
        if (it.first == key)
        {
            it.second = value;
            return;
        }
    }

    listPtr->emplace_back(key, value);
    count++;
}

template <typename Key, typename Value>
void HashTable<Key, Value>::remove(const Key& key)
{
    std::hash<Key> hasher;
    size_t index = hasher(key) % buckets.size();
    auto& listPtr = buckets[index];

    for (auto it = listPtr->begin(); it != listPtr->end();)
    {
        if (it->first == key)
        {
            it = listPtr->erase(it);
            count--;
            return;
        }
        else
        {
            it++;
        }
    }
}

template <typename Key, typename Value>
bool HashTable<Key, Value>::find(const Key& key, Value& value)
{
    std::hash<Key> hasher;
    size_t index = hasher(key) % buckets.size();
    auto& listPtr = buckets[index];
    if (nullptr != listPtr && listPtr->size())
    {
        for (auto& it : *listPtr)
        {
            if (it.first == key)
            {
                value = it.second;
                return true;
            }
        }
    }

    return false;
}

template <typename Key, typename Value>
Value& HashTable<Key, Value>::operator[](const Key& key)
{
    if ((double)count / buckets.size() >= maxLoadFactor)
    {
        resize();
    }
    std::hash<Key> hasher;
    size_t index = hasher(key) % buckets.size();
    auto& listPtr = buckets[index];
    for (auto& it : *listPtr)
    {
        if (it.first == key)
        {
            return it.second;
        }
    }

    listPtr->emplace_back(key, Value{});
    count++;

    return listPtr->back().second;
}

template <typename Key, typename Value>
void HashTable<Key, Value>::resize()
{
    const size_t oldCapacity = buckets.size();
    const size_t newCapacity = oldCapacity << 1;
    std::vector<ListPtr> newBuckets(newCapacity);
    for (auto& newBucket : newBuckets)
    {
        newBucket = std::make_shared<List>();
    }

    std::hash<Key> hasher;
    for (const auto& listPtr : buckets)
    {
        if (listPtr->empty())
            continue;
        for (auto& pair : *listPtr)
        {
            const size_t index = hasher(pair.first) % newCapacity;
            newBuckets[index]->emplace_back(std::move(pair));
        }
    }

    buckets = std::move(newBuckets);
    // size不变
}

#endif  //__HASH_TABLE_H__